Cache Missing

原文地址

Cache 的局部性

程序在一段时间内访问的数据通常具有局部性，比如对一维数组来说，访问了地址 x 上的元素，那么以后访问地址 x+1、x+2上元素的可能性就比较高

现在访问的数据，在不久之后再次被访问的可能性也比较高

局部性分为“时间局部性”和“空间局部性”，时间局部性是指当前被访问的数据随后有可能访问到

空间局部性是指当前访问地址附近的地址可能随后被访问。处理器通过在内存和核心之间增加缓存以利用局部性增强程序性能，这样可以用远低于缓存的价格换取接近缓存的速度

时间局部性

for(int x = 0; x < 100; x++) 
{
	for(int y = 0; y < 100; y++) 
	{
		... = ... array[y] ...
	}
}

for(int x = 0; x < 100; x++) 
{
	for(int y = 0; y < 100; y++) 
	{
		... = ... array[x] ...
	}
}

示例2 的性能是 示例1 的 8 倍